package com.base.dp;

/**
 * 有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 "L" 的托米诺形。两种形状都可以旋转。
 *
 *
 *
 * 给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 109 + 7 取模 的值。
 *
 * 平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。
 */
public class NumTilings {
    public static void main(String[] args) {
        NumTilings numTilings = new NumTilings();
        System.out.println(numTilings.numTilings(3));
    }
    private static final int MOD = 1000000007;
    public int numTilings(int n) {
        //初始化 DP 数组：dp[0] = 1，因为没有空间需要平铺，只有一种方法，即什么也不做。dp[1] = 1，因为只能使用一个 2 x 1 的多米诺形瓷砖。
        //状态转移：对于每个 i (从 2 到 n)，我们需要考虑以下几种情况：
        //在最后放置一个 2 x 1 的多米诺形瓷砖。
        //在最后放置两个 1 x 2 的多米诺形瓷砖，一个在另一个上方。
        //在最后放置一个 “L” 形的托米诺形瓷砖。
        //根据上述情况，我们可以得到以下状态转移方程：
        //dp[i] = dp[i - 1] + 2 * dp[i - 2]
        //dp[i - 1] 表示在最后放置一个 2 x 1 的多米诺形瓷砖。
        //2 * dp[i - 2] 表示在最后放置两个 1 x 2 的多米诺形瓷砖或者一个 “L” 形的托米诺形瓷砖。
        //由于 “L” 形的托米诺形瓷砖可以旋转，我们需要考虑其在不同旋转状态下的放置方法。
        // 实际上，对于 “L” 形的托米诺形瓷砖，当它旋转 180 度时，可以看作是两个 1 x 2 的多米诺形瓷砖的组合，因此我们在状态转移方程中已经考虑了这种情况。
        //其中 dp[i] 表示平铺 2 x i 面板的方法数量。
        if (n == 1) return 1;
        if (n == 2) return 2;

        long[] dp = new long[n + 1];
        //dp[i]表示恰好用 n 个瓷砖铺满 2×i 的地板的方法数。
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 1] * 2 + dp[i - 3]) % MOD;
        }

        return (int) dp[n];

    }
}
